package _11_整理题目._4_动态规划._子数组子矩阵;

import org.junit.Test;

/**
 * https://leetcode-cn.com/problems/maximum-length-of-subarray-with-positive-product/
 *
 * 给你一个整数数组 nums，请你求出 乘积为正数 的最长子数组的长度。
 * 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
 * 请你返回乘积为正数的最长子数组长度。
 * 注意，0 不是正数
 *
 * 输入：nums = [1,-2,-3,4]
 * 输出：4
 * 解释：数组本身乘积就是正数，值为 24 。
 *
 * 题目只问了 乘积为正数 没说最大乘积，所以只考虑 数的正负即可。
 * 状态定义，维护两个 dp 数组
 *      dpPosLen[i] 以当前位置为结尾的乘积为正数的最长子数组长度
 *      dpNegLen[i] 以当前位置为结尾的乘积为负数的最长子数组长度
 * 分类讨论
 *      当前位置 nums[i] 为0
 *          dpPosLen[i] = 0
 *          dpNegLen[i] = 0
 *      当前位置为正数
 *          dpPosLen[i] = dpPosLen[i-1] + 1
 *          if dpNegLen[i-1] == 0   则 = 0，否则 dpNegLen[i-1]+1
 *      当前位置为负数
 *          if dpPosLen[i-1] == 0   则 = 0，否则 dpNegLen[i-1]+1
 *          dpNegLen[i] = dpPosLen[i-1] + 1
 *
 *
 */
public class _04_乘积为正数的最长子数组长度 {

    public int maxFactLen(int[] nums) {
        int n = nums.length;
        int[] dpPosLen = new int[n];
        int[] dpNegLen = new int[n];
        // 初始化第一个值
        if (nums[0] > 0) {
            dpPosLen[0] = 1;
            dpNegLen[0] = 0;
        } else if (nums[0] < 0) {
            dpPosLen[0] = 0;
            dpNegLen[0] = 1;
        } else {
            dpPosLen[0] = 0;
            dpNegLen[0] = 0;
        }
        // 计算 dp，并更新 max
        int max = dpPosLen[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                dpPosLen[i] = dpPosLen[i-1]==0 ? 1 : dpPosLen[i-1]+1;
                dpNegLen[i] = dpNegLen[i-1]==0 ? 0 : dpNegLen[i-1]+1;
            } else if (nums[i] < 0) {
                dpPosLen[i] = dpNegLen[i-1]==0 ? 0 : dpNegLen[i-1]+1;
                dpNegLen[i] = dpPosLen[i-1]==0 ? 1 : dpPosLen[i-1]+1;
            } else {
                dpPosLen[i] = 0;
                dpNegLen[i] = 0;
            }
            max = Math.max(max, dpPosLen[i]);
        }
        return max;
    }

    @Test
    public void main() {
        int[] nums = {1,-2,-3,4}; // 4
        System.out.println(maxFactLen(nums));
    }
}
